#pragma once
#include <iostream>
#include <string>
#include <cstdio>
#include <ctime>
#include <assert.h>
#include <thread>
#include <mutex>
#include <unordered_map>
#include <memory>
#include <vector>

static const size_t NMEMORYLIST = 208;     // 内存块链表的数量
static const size_t MAX_SIZE = 256 * 1024; // 在ThreadCache缓存中申请的最大内存块的大小
static const size_t NPAGE = 129;
static const size_t PAGE_SHIFT = 13;

#ifdef _WIN64
#include <Windows.h>
typedef long long PAGE_ID;
#elif _WIN32
#include <Windows.h>
typedef size_t PAGE_ID;
#elif __linux__
#include <sys/mman.h>
typedef long long PAGE_ID;
#endif

// 向系统申请内存
void* SystemAlloc(size_t npage)
{
#ifdef _WIN32
    // 起始地址，字节数，属性：分配实际的物理内存、先分配虚拟内存使用是在分配，权限：读写
    void* addr = VirtualAlloc(nullptr, (npage << PAGE_SHIFT), MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#elif __linux__
    // 起始地址，字节数，权限：读写，属性 匿名映射、不写回文件，文件描述符、起始偏移量
    void* addr = mmap(nullptr, (npage << PAGE_SHIFT), PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
#endif
    return addr;
}

// 释放内存
#ifdef _WIN32
void SystemFree(void* ptr)
{
    VirtualFree(ptr, 0, MEM_RELEASE);
}
#endif

#ifdef __linux__
void* SystemFree(void* ptr, size_t size)
{
    munmap(ptr, size);
}
#endif

// 返回当前节点的下一个位置的地址
static void*& NextObj(void* obj)
{
    return *(void**)obj;
}

// 日志宏函数------------------------------------------------------------------------------------------------------------------------
#define INF 0
#define DBG 1
#define ERR 2
#define LOG_LEVEL INF

#define LOG(level, format, ...)                                                                                        \
    do                                                                                                                 \
    {                                                                                                                  \
        if (level < LOG_LEVEL)                                                                                         \
            break;                                                                                                     \
        time_t t = time(NULL);                                                                                         \
        struct tm *ltm = localtime(&t);                                                                                \
        char tmp[32] = {0};                                                                                            \
        strftime(tmp, 31, "%H:%M:%S", ltm);                                                                            \
        fprintf(stdout, "[%p %s %s:%d] " format "\n", (void *)pthread_self(), tmp, __FILE__, __LINE__, ##__VA_ARGS__); \
    } while (0)

#define INF_LOG(format, ...) LOG(INF, format, ##__VA_ARGS__)
#define DBG_LOG(format, ...) LOG(DBG, format, ##__VA_ARGS__)
#define ERR_LOG(format, ...) LOG(ERR, format, ##__VA_ARGS__)

// 内存块链表类------------------------------------------------------------------------------------------------------------------------
class MemoryList
{
private:
    void* _head = nullptr; // 链表的起始地址
    size_t _size = 0;      // 内存块个数
    size_t _maxSize = 1;   // 一个可以向中心缓存索要的最多的内存块个数

public:
    // 返回内存块个数
    size_t Size() { return _size; }
    // 返回maxSize大小
    size_t& MaxSize() { return _maxSize; }
    // 判空
    bool Empty() { return _head == nullptr; }

    // 移除内存块
    void* Pop()
    {
        assert(_head != nullptr);
        // 头删
        void* tmp = _head;
        _head = NextObj(tmp);
        NextObj(tmp) = nullptr;
        // 更新数据
        --_size;
        // 返回内存块地址
        return tmp;
    }
    void PopRange(void* start, void* end, size_t num)
    {
        assert(num <= _size);
        // 头删
        start = _head;
        end = _head;
        for (size_t i = 0; i < num - 1; i++)
        {
            end = NextObj(end);
        }
        _head = NextObj(end);
        NextObj(end = nullptr);
        // 更新数据
        _size -= num;
    }
    // 添加内存块
    void Push(void* obj)
    {
        assert(obj);
        // 头插
        NextObj(obj) = _head;
        _head = obj;
        // 更新数据
        ++_size;
    }
    void PushRange(void* start, void* end, size_t num)
    {
        // 头插
        NextObj(end) = _head;
        _head = start;
        // 更新数据
        _size += num;
    }
};

// 工具类------------------------------------------------------------------------------------------------------------------------
class Util
{
public:
    // 内存对齐函数
    static inline size_t RoundUp(size_t size)
    {
        if (size <= 128)
            return _RoundUp(size, 8);
        else if (size <= 1024)
            return _RoundUp(size, 16);
        else if (size <= 8 * 1024)
            return _RoundUp(size, 128);
        else if (size <= 64 * 1024)
            return _RoundUp(size, 1024);
        else if (size <= 256 * 1024)
            return _RoundUp(size, 8 * 1024);
        // 大于256KB的内存对齐
        else
        {
            // 对齐数为1<<13即可
            return _RoundUp(size, 1 << PAGE_SHIFT);
        }
    }
    static inline size_t _RoundUp(size_t size, size_t alignment_number)
    {
        // 如果有余数的话，就需要进行内存对齐
        if (size % alignment_number)
            return (size / alignment_number + 1) * alignment_number;
        // 如果可以整除的话，就不需要内存对齐了
        else
            return size;
    }

    // 内存块链表桶映射下标
    static inline size_t HashIndex(size_t size)
    {
        // 各个区间中内存块链表的个数
        static const size_t range_number_array[5] = { 16, 56, 56, 56, 56 };

        if (size <= 128)
            return _HashIndex(size, 8);
        else if (size <= 1024)
            return _HashIndex(size - 128, 16) + range_number_array[0];
        else if (size <= 8 * 1024)
            return _HashIndex(size - 1024, 128) + range_number_array[0] + range_number_array[1];
        else if (size <= 64 * 1024)
            return _HashIndex(size - 8 * 1024, 1024) + range_number_array[0] + range_number_array[1] + range_number_array[2];
        else if (size <= 256 * 1024)
            return _HashIndex(size - 64 * 1024, 8 * 1024) + range_number_array[0] + range_number_array[1] + range_number_array[2] + range_number_array[3];
        else
        {
            abort();
        }
    }
    static inline size_t _HashIndex(size_t size, size_t alignment_number)
    {
        // 如果有余数的话，就+1, 但是数组的下标是从0开始的，所以就不加1了
        if (size % alignment_number)
            return (size / alignment_number);
        else
            return (size / alignment_number) - 1;
    }

    // 计算一次向中心缓存申请多少个内存块
    static inline size_t AllocNumFromCentralCache(size_t memory_max_size, size_t size)
    {
        size_t num = MAX_SIZE / size;
        // 将个数控制在【2，512】之间
        if (num < 2)
            num = 2;
        else if (num > 512)
            num = 512;
        // 返回小的值
        return min(memory_max_size, num);
    }

    // 计算向页缓存内存池申请一个span切割成size大小的内存块时，申请多大页的span
    static inline size_t MovePageNum(size_t size)
    {
        // 计算size大小的内存块申请时，线程内存池向中心缓存一次最多要多少空间
        size_t n = AllocNumFromCentralCache(-1, size);
        size_t bytes = n * size;
        // 计算要用多少个页
        size_t npage = (bytes >> PAGE_SHIFT);
        return npage == 0 ? 1 : npage;
    }
};

// 定长内存池-----------------------------------------------------------------------------------------------------------------------
template <class T>
class FixedLengthMemoryPoll
{
private:
    char* _head = nullptr;   // 大内存块
    void* _freelist = nullptr;    // 还回来的小的内存块
    size_t _remain_byte = 0; // 大内存块剩余的大小

public:
    // 申请内存
    T* New()
    {
        T* obj = nullptr;
        // 如果free链表中有剩余，那么优先从这里面分配内存
        if (_freelist)
        {
            void* next = *((void**)_freelist);
            obj = (T*)_freelist;
            _freelist = next;
        }
        // 没有的话，就在大块内存中切
        else
        {
            // 如果大块内存不够了的话，就舍弃剩余内存，在向系统申请一块大内存
            if (_remain_byte < sizeof(T))
            {
                _remain_byte = 128 * 1024;
                _head = (char*)SystemAlloc(_remain_byte >> PAGE_SHIFT);
                if (_head == nullptr)
                    throw std::bad_alloc();
            }
            // 切分
            obj = (T*)_head;
            size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);
            _head += objSize;

            _remain_byte -= objSize;

        }
        new(obj)T;
        return obj;
    }
    // 释放内存
    void Delete(T* obj)
    {
        // 调用析构函数--不会将动态申请的内存空间还给os，delete才会这样做
        obj->~T();
        NextObj(obj) = _freelist;
        _freelist = obj;
    }
};

struct Span;
class ThreadCache;

FixedLengthMemoryPoll<Span> SpanPool;
FixedLengthMemoryPoll<ThreadCache> ThreadCachePool;

// 页单位的内存块类-----------------------------------------------------------------------------------------------------------------------
struct Span
{
    PAGE_ID _id = 0;      // 页号
    size_t _num = 0;      // 页数
    size_t _objSize = 0;  // 小内存块的大小
    size_t _useCount = 0; // 小内存块被使用的个数

    Span* _next = nullptr;
    Span* _prev = nullptr;
    void* _memorylist = nullptr; // 小内存块链表

    bool _isUse = false; // 是否被使用
};

// 管理span的链表类-----------------------------------------------------------------------------------------------------------------------
// 带头双向循环链表
class SpanList
{
private:
    Span* _head; // 头节点
public:
    std::mutex _mutex; // 桶锁

public:
    SpanList()
    {
        _head = SpanPool.New();
        _head->_next = _head;
        _head->_prev = _head;
    }
    // 迭代器
    Span* begin() { return _head->_next; }
    Span* end() { return _head; }

    // 插入一个Span
    void Push(Span* span)
    {
        assert(span);
        assert(span != _head);
        // 头插
        Span* Next = _head->_next;

        span->_next = Next;
        span->_prev = _head;
        _head->_next = span;
        Next->_prev = span;
    }

    // 移除一个span
    Span* Pop()
    {
        assert(!Empty());
        Span* cur = _head->_next;
        Span* Next = cur->_next;

        // 移除
        _head->_next = Next;
        Next->_prev = _head;
        cur->_prev = nullptr;
        cur->_next = nullptr;
        // 返回span
        return cur;
    }

    // 移除一个指定的span
    void Erase(Span* span)
    {
        assert(span);
        assert(span != _head);
        Span* Next = span->_next;
        Span* Prev = span->_prev;

        // 移除
        Prev->_next = Next;
        Next->_prev = Prev;
    }

    // 判空
    bool Empty()
    {
        return _head->_next == _head;
    }
};

// 页缓存内存池模块------------------------------------------------------------------------------------------------------------------------------------
class PageCache
{
private:
    static PageCache _istance;      // 单例对象
    SpanList _page_spanlist[NPAGE]; // span桶

    std::unordered_map<PAGE_ID, Span*> _idSpanMap; // 存放Span和PAGE_ID的映射关系

public:
    std::mutex _page_mutex;

private:
    // 单例模式
    PageCache() = default;
    PageCache(const PageCache&) = delete;

public:
    // 获取单例对象
    static PageCache& GetInstance()
    {
        return _istance;
    }

    // 给中心缓存一个span
    Span* GetNewSpan(size_t npage)
    {
        assert(npage);
        // 大于128页的内存申请
        if (npage > NPAGE - 1)
        {
            void* ptr = SystemAlloc(npage);
            // 创建一个Span用来管理申请来的内存块
            Span* newSpan = SpanPool.New();
            // 更新数据
            newSpan->_id = (PAGE_ID)ptr >> PAGE_SHIFT;
            newSpan->_num = npage;

            // 添加映射关系
            _idSpanMap[newSpan->_id]  = newSpan;
            return newSpan;
        }
        // 小于128页的空间申请
        // 对于256KB以内的，会通过三层结构申请并连接到线程内存池中
        // 大于256KB小于128页的则是，在申请空间时，之间在页缓存中调用
        else
        {
            // 先在npage的链表上有span
            if (!_page_spanlist[npage].Empty())
            {
                // 有span,取下来直接返回就可以了
                Span* nSpan = _page_spanlist[npage].Pop();
                // 建立映射
                for (size_t i = 0; i < nSpan->_num; i++)
                {
                    _idSpanMap[nSpan->_id + i]  = nSpan;
                }
                return nSpan;
            }
            // 如果没有的话，就在后面的链表中找一个比n大的span，进行切分
            for (int i = npage + 1; i < NPAGE; i++)
            {
                // 找到了
                if (!_page_spanlist[i].Empty())
                {
                    // 取出来Span
                    Span* kSpan = _page_spanlist[i].Pop();
                    Span* nSpan = SpanPool.New();

                    // 切分
                    nSpan->_id = kSpan->_id;
                    nSpan->_num = npage;

                    kSpan->_id += npage;
                    kSpan->_num -= npage;

                    // 建立映射关系
                    for (size_t j = 0; j < nSpan->_num; j++)
                    {
                        _idSpanMap[nSpan->_id + j] = nSpan;
                    }
                    _idSpanMap[kSpan->_id] = kSpan;
                    _idSpanMap[kSpan->_id + kSpan->_num - 1] = kSpan;

                    //for (auto it : _idSpanMap)
                    //{
                    //    std::cout << it.first << ":" << it.second->_id << std::endl;
                    //}

                    // 将剩余的span放到指定的位置
                    _page_spanlist[kSpan->_num].Push(kSpan);

                    return nSpan;
                }
            }
            // 如果没有可用的Span的话，就向内存申请一个128页的Span
            Span* bigSpan = SpanPool.New();
            void* addr = SystemAlloc(NPAGE - 1);
            // 将地址转化为页号
            bigSpan->_id = (PAGE_ID)addr >> PAGE_SHIFT;
            bigSpan->_num = NPAGE - 1;
            // 放入到链表中
            _page_spanlist[bigSpan->_num].Push(bigSpan);

            return GetNewSpan(npage);
        }
    }
    // 地址和span的映射关系
    Span* MapObjectToSpan(void* start)
    {
        // 计算页号
        PAGE_ID id = (PAGE_ID)start >> PAGE_SHIFT;

        // 加锁
        std::unique_lock<std::mutex> _lock(_page_mutex);
        std::unordered_map<PAGE_ID, Span*>::iterator it = _idSpanMap.find(id);
        if (it == _idSpanMap.end())
        {
            assert(false);
        }
        return it->second;
    }
    // 将span还给页缓存
    void ReleaseSpanToPageCache(Span* span)
    {
        assert(span);
        // 大于128页的空间回收
        if (span->_objSize > MAX_SIZE)
        {
            void* ptr = (void*)(span->_id << PAGE_SHIFT);
            SystemFree(ptr);
            // 释放掉Span
            SpanPool.Delete(span);
        }
        // 向前合并
        while (1)
        {
            PAGE_ID prev_id = span->_id - 1;
            // 找span前面的一个span
            auto it = _idSpanMap.find(prev_id);
            // 没找到
            if (it == _idSpanMap.end())
                break;
            Span* prev_span = it->second;
            // 如果前面的span在使用就不合并了
            if (prev_span->_isUse == true)
                break;
            // 如果两个span加起来大于NPAGE了，也就不合并了
            if (prev_span->_num + span->_num > NPAGE - 1)
                break;

            // 合并
            span->_id = prev_span->_id;
            span->_num += prev_span->_num;

            // 将prev_span移除
            _page_spanlist[prev_span->_num].Erase(prev_span);
            SpanPool.Delete(prev_span);
        }
        // 向后合并
        while (1)
        {
            PAGE_ID next_id = span->_id + span->_num;
            // 找span后面的一个span
            auto it = _idSpanMap.find(next_id);
            // 没找到
            if (it == _idSpanMap.end())
                break;
            Span* next_span = it->second;
            // 如果后面的span在使用就不合并了
            if (next_span->_isUse == true)
                break;
            // 如果两个span加起来大于NPAGE了，也就不合并了
            if (next_span->_num + span->_num > NPAGE - 1)
                break;

            // 合并
            span->_num += next_span->_num;

            // 将next_span移除
            _page_spanlist[next_span->_num].Erase(next_span);
            SpanPool.Delete(next_span);
        }
        // 更新数据
        span->_isUse = false;
        // 放入到新的链表中
        _page_spanlist[span->_num].Push(span);
        // 建立新映射
        _idSpanMap[span->_id] = span;
        _idSpanMap[span->_id + span->_num - 1] =  span;
    }
};

// 初始化静态成员
PageCache PageCache::_istance;

// 中心缓存内存池模块------------------------------------------------------------------------------------------------------------------------------------
class CentralCache
{
private:
    static CentralCache _istance; // 单例对象
    SpanList _spanlist[NMEMORYLIST];

private:
    // 单例模式
    CentralCache() = default;
    CentralCache(const CentralCache&) = delete;

public:
    // 获取单例对象
    static CentralCache& GetInstance()
    {
        return _istance;
    }

    // 提供内存块给线程内存池
    size_t ProvideThreadCacheMemory(void*& start, void*& end, size_t num, size_t size)
    {
        // 判断在哪个桶里面
        size_t hash_index = Util::HashIndex(size);

        // 开始进行桶内部操作了，需要加锁
        _spanlist[hash_index]._mutex.lock();
        // 获取一个Span内存块
        Span* span = GetOneSpan(size, hash_index);
        assert(span);
        assert(span->_memorylist);

        // 切分num个内存块下来
        start = span->_memorylist;
        end = start;
        size_t actual_num = 1;
        while (actual_num < num && NextObj(end) != nullptr)
        {
            ++actual_num;
            end = NextObj(end);
        }
        span->_memorylist = NextObj(end);
        NextObj(end) = nullptr;

        // 解锁
        _spanlist[hash_index]._mutex.unlock();
        return actual_num;
    }

    // 找到一个可用的Span
    Span* GetOneSpan(size_t size, size_t index)
    {
        // 在spanlist中找到一个可用的span
        Span* it = _spanlist[index].begin();
        while (it != _spanlist[index].end())
        {
            if (it->_memorylist != nullptr)
            {
                return it;
            }
            else
            {
                it = it->_next;
            }
        }
        // 没有的话，先解除桶锁，加页缓存锁，之后向页缓存申请
        _spanlist[index]._mutex.unlock();
        PageCache::GetInstance()._page_mutex.lock();
        Span* newSpan = PageCache::GetInstance().GetNewSpan(Util::MovePageNum(size));
        // 更新数据
        newSpan->_isUse = true;
        newSpan->_objSize = size;
        // 解锁
        PageCache::GetInstance()._page_mutex.unlock();

        // 对新获取的span进行内存块切分
        // 确定内存块首尾的位置
        char* start = (char*)(newSpan->_id << PAGE_SHIFT);
        size_t bytes = newSpan->_num << PAGE_SHIFT;
        char* end = start + bytes;
        // 切分
        newSpan->_memorylist = start;
        char* fast = start + size;
        void* slow = start;

        while (fast < end)
        {
            NextObj(slow) = fast;
            slow = fast;
            fast += size;
        }
        NextObj(slow) = nullptr;

        // 加桶锁
        _spanlist[index]._mutex.lock();
        // 将新的span链接上去
        _spanlist[index].Push(newSpan);

        return newSpan;
    }

    // 线程内存池将多余的内存块还回来
    void ReturnCentralCacheMemory(void* start, size_t size)
    {
        // 找到对应的桶
        size_t hash_index = Util::HashIndex(size);
        // 加锁
        _spanlist[hash_index]._mutex.lock();
        // 遍历每一个内存块吗，放到原来对应的span的位置
        while (start)
        {
            // 找到该内存块对应的span
            Span* span = PageCache::GetInstance().MapObjectToSpan(start);
            // 头插
            NextObj(start) = span->_memorylist;
            span->_memorylist = start;
            // 更新数据
            span->_useCount--;

            // 如果该span的内存块全部都还回来了，那么就将该span还给页缓存内存池
            if (span->_useCount == 0)
            {
                // 先将span取出来
                _spanlist[hash_index].Erase(span);
                // 更新span的变量
                span->_memorylist = nullptr;
                span->_next = nullptr;
                span->_prev = nullptr;
                // 解除桶锁,上页缓存锁
                _spanlist[hash_index]._mutex.unlock();
                PageCache::GetInstance()._page_mutex.lock();
                // 将span还给PgaeCache
                PageCache::GetInstance().ReleaseSpanToPageCache(span);
                // 解锁，上桶锁
                PageCache::GetInstance()._page_mutex.unlock();
                _spanlist[hash_index]._mutex.lock();
            }
            start = NextObj(start);
        }
        // 解桶锁
        _spanlist[hash_index]._mutex.unlock();
    }
};

// 初始化静态成员
CentralCache CentralCache::_istance;

// 线程内存池模块------------------------------------------------------------------------------------------------------------------------------------
class ThreadCache
{
private:
    MemoryList _memorylist[NMEMORYLIST];

public:
    // 线程申请内存
    void* Allocate(size_t size)
    {
        assert(size <= MAX_SIZE);
        // 进行内存对齐和下标映射
        size_t alignment_size = Util::RoundUp(size);
        size_t hash_index = Util::HashIndex(size);

        // 在对应的内存块链表中找内存块
        // 有内存块
        if (!_memorylist[hash_index].Empty())
        {
            return _memorylist[hash_index].Pop();
        }
        // 向中心缓存申请内存块
        else
        {
            return FetchMemoryFromCentralCache(alignment_size, hash_index);
        }
    }
    // 向中心缓存申请内存块
    void* FetchMemoryFromCentralCache(size_t size, size_t index)
    {
        // 慢启动的方式申请内存块
        // 计算一次申请的内存块个数
        size_t batch_num = Util::AllocNumFromCentralCache(_memorylist[index].MaxSize(), size);
        // 如果最小值是内存块链表中记录的值，那么就将链表中记录的可申请的个数最大值加1
        if (batch_num == _memorylist[index].MaxSize())
        {
            _memorylist[index].MaxSize()++;
        }

        // 申请内存
        void* start = nullptr;
        void* end = nullptr;
        // 返回的是实际申请到的个数
        size_t actural_num = CentralCache::GetInstance().ProvideThreadCacheMemory(start, end, batch_num, size);
        assert(actural_num > 0);

        // 如果是申请了一个内存块直接返回即可
        if (actural_num == 1)
        {
            assert(start == end);
            return start;
        }
        // 如果是申请了多个内存块的话，取出第一个返回，其他的挂到内存块链表中
        else
        {
            _memorylist[index].PushRange(NextObj(start), end, actural_num - 1);
            NextObj(start) = nullptr;
            return start;
        }
    }

    // 线程释放内存块
    void Deallocate(void* ptr, size_t size)
    {
        assert(ptr);
        // 找到下标
        size_t hash_index = Util::HashIndex(size);
        // 将内存块放回到链表中
        _memorylist[hash_index].Push(ptr);

        // 如果链表过长的话，就换给中心缓存
        if (_memorylist[hash_index].Size() >= _memorylist[hash_index].MaxSize())
        {
            ListToLong(_memorylist[hash_index], size);
        }
    }
    // 如果链表过长的话，就换给中心缓存
    void ListToLong(MemoryList& memorylist, size_t size)
    {
        // 将内存块从链表中拿出来
        void* start = nullptr;
        void* end = nullptr;
        memorylist.PopRange(start, end, memorylist.MaxSize());

        // 还给中心缓存
        CentralCache::GetInstance().ReturnCentralCacheMemory(start, size);
    }
};

// 线程局部存储
static _declspec(thread) ThreadCache* _pTLSThreadCache = nullptr;

// 对外提供的申请内存和释放内存的函数---------------------------------------------------------------------------------------------------------
// 申请内存
void* TcMalloc_Allocate(size_t size)
{
    // 在256KB之内的空间申请
    if (size < MAX_SIZE)
    {
        if (_pTLSThreadCache == nullptr)
        {
            _pTLSThreadCache = ThreadCachePool.New();
        }
        return _pTLSThreadCache->Allocate(size);
    }
    // 大于256KB的空间申请--直接去页缓存申请空间
    else
    {
        // 内存对齐
        size_t alignment_size = Util::RoundUp(size);
        // 确定申请的空间对应多少页
        size_t npage = alignment_size >> PAGE_SHIFT;
        // 加锁
        PageCache::GetInstance()._page_mutex.lock();
        // 申请空间
        Span* span = PageCache::GetInstance().GetNewSpan(npage);
        // 解锁
        PageCache::GetInstance()._page_mutex.unlock();
        // 更新数据--方便释放时，知道内存块的大小
        span->_objSize = size;

        void* ptr = (void*)(span->_id << PAGE_SHIFT);
        return ptr;
    }
}

// 释放内存
void TcMalloc_Deallocate(void* ptr)
{
    // 获取内存块大小
    Span* span = PageCache::GetInstance().MapObjectToSpan(ptr);
    size_t size = span->_objSize;

    // 小于256KB的内存回收
    if (size <= MAX_SIZE)
    {
        assert(_pTLSThreadCache != nullptr);
        _pTLSThreadCache->Deallocate(ptr, size);
    }
    // 大于256KB的内存回收
    else
    {
        // 加锁
        PageCache::GetInstance()._page_mutex.lock();
        // 回收空间
        PageCache::GetInstance().ReleaseSpanToPageCache(span);
        // 解锁
        PageCache::GetInstance()._page_mutex.unlock();
    }
}

//多线程下用tcmalloc申请和释放内存
//多少个线程，申请和释放内存多少轮，每轮多少次
void TestTcMalloc(size_t thread_num, size_t round_num, size_t count)
{
    std::vector<std::thread> threads(thread_num); 

    //申请消耗的时间
    size_t allocate_time = 0;
    //释放消耗的时间
    size_t deallocate_time = 0;

    for (size_t i = 0; i < thread_num; i++)
    {
        threads[i] = std::thread([&, i]() {
            std::vector<void*> v;
            v.reserve(count);

            for (size_t j = 0; j < round_num; j++)
            {
                //申请内存
                size_t begin1 = clock();
                for (size_t k = 0; k < count; k++)
                {
                    v.push_back(TcMalloc_Allocate(16));
                }
                size_t end1 = clock();

                //释放内存
                size_t begin2 = clock();
                for (size_t k = 0; k < count; k++)
                {
                    TcMalloc_Deallocate(v[k]);
                }
                size_t end2 = clock();

                //累计时间
                allocate_time += (end1 - begin1);
                deallocate_time += (end2 - begin2);
            }
            });
    }
    for (auto& t : threads)
    {
        t.join();
    }

    printf("%u个线程并发执行%u轮次，每轮malloc %u次，花费：%u ms\n", thread_num, round_num, count, allocate_time);
    printf("%u个线程并发执行%u轮次，每轮free %u次，花费：%u ms\n", thread_num, round_num, count, deallocate_time);
    printf("%u个线程并发执行malloc&free %u次, 共花费时间：%u ms\n", thread_num, thread_num * round_num * count, allocate_time + deallocate_time);

}

//malloc
void TestMalloc(size_t thread_num, size_t round_num, size_t count)
{
    std::vector<std::thread> threads(thread_num);

    //申请消耗的时间
    size_t allocate_time = 0;
    //释放消耗的时间
    size_t deallocate_time = 0;

    for (size_t i = 0; i < thread_num; i++)
    {
        threads[i] = std::thread([&, i]() {
            std::vector<void*> v;
            v.reserve(count);

            for (size_t j = 0; j < round_num; j++)
            {
                //申请内存
                size_t begin1 = clock();
                for (size_t k = 0; k < count; k++)
                {
                    v.push_back(malloc(16));
                }
                size_t end1 = clock();

                //释放内存
                size_t begin2 = clock();
                for (size_t k = 0; k < count; k++)
                {
                    free(v[k]);
                }
                size_t end2 = clock();
                v.clear();
                //累计时间
                allocate_time += (end1 - begin1);
                deallocate_time += (end2 - begin2);
            }
            });

    }
    for (auto& t : threads)
    {
        t.join();
    }


    printf("%u个线程并发执行%u轮次，每轮malloc %u次，花费：%u ms\n", thread_num, round_num, count, allocate_time);
    printf("%u个线程并发执行%u轮次，每轮free %u次，花费：%u ms\n", thread_num, round_num, count, deallocate_time);
    printf("%u个线程并发执行malloc&free %u次, 共花费时间：%u ms\n", thread_num, thread_num*round_num*count, allocate_time + deallocate_time);
}

int main()
{
    int thread_num = 10000;
    std::cout << "===================================================" << std::endl;
    std::cout << "申请固定大小16KB的测试" << std::endl;
    //TestTcMalloc(thread_num, 4, 10);
    //std::cout << std::endl << std::endl;
    TestMalloc(thread_num, 4, 10);
    std::cout << std::endl;
    std::cout << "===================================================" << std::endl;

    return 0;
 }

//int main()
//{
//    std::vector<void*> v;
//    v.reserve(1000);
//    
//    //申请内存
//    for (int i = 0; i < 1000; i++)
//    {
//        if (i == 512)
//        {
//            int x = 0;
//        }
//        v.push_back(TcMalloc_Allocate(16));
//    }
//
//    for (int i = 0; i < 1000; i++)
//    {
//        TcMalloc_Deallocate(v[i]);
//    }
//    return 0;
//}